package com.jeff.game.tools.physics;

import java.util.HashSet;
import java.util.Set;

/**
 * A tree representing 2D screen space. Each node has four children, one for
 * each Region
 */
public class QuadTree
{
  private final Set<Rigid> rigids = new HashSet<Rigid>();

  private final Box box;
  private final Box[] subboxes;

  private final QuadTree[] subtrees = new QuadTree[Region.values().length];

  /**
   * @param box Box that represents this node
   */
  public QuadTree(Box box)
  {
    this.box = box;
    this.subboxes = box.quarter();
  }

  /**
   * Adds a rigid body to this tree. The rigid body must be inside the box
   * representing this node.
   * @param rigid Rigid body
   * @return True if the rigid body was added, false, otherwise
   */
  public boolean add(Rigid rigid)
  {
    if (box.isContains(rigid.getEnclosingBox()))
    {
      rigids.add(rigid);

      for (int i = 0; i < Region.values().length; ++i)
      {
        QuadTree subtree = getSubtree(i);
        subtree.add(rigid);
      }

      return true;
    }
    else
    {
      return false;
    }
  }

  private QuadTree getSubtree(int index)
  {
    if (subtrees[index] == null)
    {
      subtrees[index] = new QuadTree(subboxes[index]);
    }

    return subtrees[index];
  }

  /**
   * Finds potential overlaps
   * @param rigid Rigid
   * @return Set of Rigids that the given Rigid may overlap with
   */
  public Set<Rigid> getPotentialOverlaps(Rigid rigid)
  {
    Set<Rigid> results = new HashSet<Rigid>();

    if (rigids.contains(rigid))
    {
      results.addAll(rigids);
      results.remove(rigid);

      pruneNonNeighbors(rigid, results);
    }

    return results;
  }

  private void pruneNonNeighbors(Rigid rigid, Set<Rigid> results)
  {
    QuadTree subtree = getContainingSubtree(rigid);

    if (subtree != null)
    {
      pruneSiblings(subtree, results);
      subtree.pruneNonNeighbors(rigid, results);
    }
  }

  private void pruneSiblings(QuadTree subtree, Set<Rigid> results)
  {
    for (QuadTree t : subtrees)
    {
      if (t != null && !subtree.equals(t))
      {
        results.removeAll(t.rigids);
      }
    }
  }

  private QuadTree getContainingSubtree(Rigid rigid)
  {
    for (int i = 0; i < Region.values().length; ++i)
    {
      if (subboxes[i].isContains(rigid))
      {
        return getSubtree(i);
      }
    }

    return null;
  }
}
